import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
class Codec {
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        return front(root,"");
    }
    public String front(TreeNode root,String str){
        if(root==null){
            str=str+"tmp,";
        }else{
            str+=str.valueOf(root.val)+",";
            str=front(root.left,str);
            str=front(root.right,str);
        }
        return str;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] str=data.split(",");
        List<String> list=new LinkedList<>(Arrays.asList(str));
        return back(list);
    }
    public TreeNode back(List<String> list){
        if(list.get(0).equals("tmp")){
            list.remove(0);
            return null;
        }
        TreeNode root=new TreeNode(Integer.parseInt(list.get(0)));
        list.remove(0);
        root.left=back(list);
        root.right=back(list);
        return root;
    }
}




















class Codec1 {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        return front(root,"");
    }

    public String front(TreeNode root,String str){
        if(root==null){
            str+="None";
        }else{
            str+=str.valueOf(root.val)+",";
            str=front(root.left,str);
            str=front(root.right,str);
        }
        return str;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] str=data.split(",");
        List<String> list=new LinkedList<String>(Arrays.asList(str));
        return back(list);
    }
    public TreeNode back(List<String> list){
        if(list.get(0).equals("None")){
            list.remove(0);
            return null;
        }
        TreeNode root=null;
        if(list.size()>0){
            root=new TreeNode(Integer.valueOf(list.get(0)));
            list.remove(0);
            root.left=back(list);
            root.right=back(list);
        }
        return root;
    }
}











public class project {
    int row;
    int col;
    boolean[][] flag;
    int min;
    public int[][] updateMatrix(int[][] mat) {
        row=mat.length;
        col=mat[0].length;
        flag=new boolean[row][col];
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(mat[i][j]==1){
                   min=Integer.MAX_VALUE;
                   dfs(mat,i,j,0);
                   mat[i][j]=min;
                }
            }
        }
        return mat;
    }
    public void dfs(int[][] arr,int x,int y,int count){
        if(x<0||y<0||x>=row||y>=col||flag[x][y]){
            return;
        }
        if(count>min){
            return;
        }
        if(arr[x][y]==0){
            min=Math.min(min,count);
            return;
        }
        flag[x][y]=true;
        dfs(arr,x+1,y,count+1);
        dfs(arr,x-1,y,count+1);
        dfs(arr,x,y+1,count+1);
        dfs(arr,x,y-1,count+1);
        flag[x][y]=false;
    }




















    private int min1;
    public int[][] updateMatrix1(int[][] mat) {
        int row=mat.length;
        int col=mat[0].length;
        boolean[][] flag=new boolean[row][col];
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(mat[i][j]==1){
                    min1=Integer.MAX_VALUE;
                    dfs1(mat,i,j,row,col,flag,0);
                    mat[i][j]=min1;
                }
            }
        }
        return mat;
    }
    public void dfs1(int[][] mat,int x,int y,int row,int col,boolean[][] flag,int count){
        if(x<0||y<0||x>=row||y>=col||flag[x][y]){
            return;
        }
        if(min1>count){
            return;
        }
        if(mat[x][y]==0) {
            min1 = Math.min(count, min1);
            return;
        }
        flag[x][y]=true;
        dfs1(mat,x+1,y,row,col,flag,count+1);
        dfs1(mat,x-1,y,row,col,flag,count+1);
        dfs1(mat,x,y+1,row,col,flag,count+1);
        dfs1(mat,x,y-1,row,col,flag,count+1);
        flag[x][y]=false;
    }














    public int projectionArea(int[][] grid) {
        int ret=0;
        for(int i=0;i<grid.length;i++){
            int row=0;
            int col=0;
            for(int j=0;j<grid.length;j++){
                if(grid[i][j]>0){
                    ret++;
                }
                row=Math.max(grid[i][j],row);
                col=Math.max(grid[j][i],col);
            }
            ret+=row+col;
        }
        return ret;
    }
}
